package simple;

/**
 *
 * {@link
 * https://www.nowcoder.com/practice/459bd355da1549fa8a49e350bf3df484?tpId=188&&tqId=38594&rp=1&ru=/activity/oj&qru=/ta/job-code-high-week/question-ranking}
 *
 *描述
 * 输入一个长度为n的整型数组array，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
 * 数据范围:
 * 1 <= n <= 10^51<=n<=10
 * 5
 * -100 <= a[i] <= 100−100<=a[i]<=100
 * 要求:时间复杂度为 O(n)O(n)，空间复杂度为 O(n)O(n)
 * 进阶:时间复杂度为 O(n)O(n)，空间复杂度为 O(1)O(1)
 * 示例1
 * 输入：
 * [1,-2,3,10,-4,7,2,-5]
 * 返回值：
 * 18
 * 说明：
 * 经分析可知，输入数组的子数组[3,10,-4,7,2]可以求得最大和为18
 *
 * @author WangZhiJian
 * @since 2022/1/4
 */
public class 连续子数组的最大和 {
    /**
     * 贪心
     * 加入当前在第n位
     * n-1的最优解若大于等于0,则可取,
     * 反之比较前方值与当前值 的大小,若前方值大,则标记该值为最优解,并以n位置重新开始
     * @param array
     *
     * 运行时间：163ms
     * 超过2.27% 用Java提交的代码
     * 占用内存：22524KB
     * 超过0.76%用Java提交的代码
     */
    public static int FindGreatestSumOfSubArray(int[] array) {
        if(array == null || array.length == 0)
            return 0;
        int best = array[0];
        int current = array[0];
        for (int i = 1; i < array.length; i++) {
            if(current > 0)
                current += array[i];
            else
                current = array[i];

            if(current > best)
                best = current;
        }

        return best;
    }
}
